import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.TreeSet;

import pl.matt.model.Testowa;

class T {

	public T() {

	}

	public T(String f) {

	}

	public String toString() {
		return "Dupa";
	}

	public void ok() {
	}

	public short getO() throws LL {
		return 9;
	}
}

class LL extends Exception {

}

class LLL extends LL {

}

class TT extends T {

	public TT() {
		super(null);
	}

	public void ok() {
		super.ok();
	}

	public short getO() {
		return 9;
	}
}

abstract class GY {

	public void u() {

	}
}

class LLinkedList

{

	class Node

	{
		public Object data;
		public Node next;
	}

	public Node head = null;

	public static LLinkedList reverseIteratively(LLinkedList list)

	{
		if (list.head == null || list.head.next == null) {
			return list;
		} else {
			Node tmp = list.head;
			Node tmp2 = list.head.next;
			tmp.next = null;
			while (tmp2 != null) {
				Node next = tmp2.next;
				tmp2.next = tmp;
				tmp = tmp2;
				tmp2 = next;
			}
			list.head = tmp;
		}
		
		return list;
	}

	private static Node reverse(Node node, Node node2) {
		if(node2 == null) {
			return node;
		} else {
			Node next = node2.next;
			node2.next = node;
			return reverse(node2, next);
		}
	}

	public static LLinkedList reverseRecursively(LLinkedList list)

	{
		if (list.head == null || list.head.next == null) {
			
		} else {
			Node oldHead = list.head;
			list.head = reverse(list.head, list.head.next);
			oldHead.next = null;
		}
		return list;
	}
}

class MessageQueue {

	private LinkedList<Object> list = new LinkedList<Object>();

	public synchronized void add(Object add) throws Exception {
		list.add(add);
		this.notify();
	}

	public synchronized Object remove() throws Exception {

		while (list.size() == 0) {
			this.wait();
		}

		return list.removeFirst();
	}
}

interface OO {
	T t = new T();
}

public class Fsdesd {

	public void f() {
		Testowa f = new Testowa();
	}

	static class Watek extends Thread {

		private MessageQueue mq;

		public Watek(MessageQueue mq) {
			this.mq = mq;
		}

		public void run() {

			try {
				System.err.println("Watek " + mq.remove());

				mq.add("cztery");

				System.err.println("Watek " + mq.remove());
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}
	
	public static void print(LLinkedList.Node n) {
		if(n != null) {
			System.err.println(n.data + " ");
			print(n.next);
		}
	}
	
	public static String removeCharacters( String s1, String s2) {

	    HashSet<Character> set = new HashSet<Character>();

	    for(char c : s2.toCharArray()) {
	        set.add(c);
	    }

	    StringBuilder sb = new StringBuilder();
	    for(char c : s1.toCharArray()) {
	        if(!set.contains(c)) {
	            sb.append(c);
	        }
	    }

	    return sb.toString();
	}
	
	static class Tree {
	    int value;
	    Tree right, left;
	    
	    public Tree(int value) {
	    	this.value = value;
	    }
	}
	
	static class NotBSTTree extends Exception {
		
	}
	
	public static Integer isBSTTree(Tree node) throws NotBSTTree {
		
		Integer result = node.value;
		if(node.left != null) {
			Integer leftMax = isBSTTree(node.left);
			if(leftMax > result) {
				throw new NotBSTTree();
			}
		}
		
		if(node.right != null) {
			Integer rightMax = isBSTTree(node.right);
			if(rightMax < result) {
				throw new NotBSTTree();
			}
			result = rightMax;
		}
		
		return result;
	}


	public static void main(String[] args) throws Exception {
		
		Tree a1 = new Tree(3);
		Tree a2 = new Tree(6);
		Tree a3 = new Tree(4);
		Tree a4 = new Tree(7);
		Tree a5 = new Tree(16);
		Tree a6 = new Tree(20);
		
		a3.left = a1;
		a3.right = a2;
		a4.left = a3;
		a4.right = a5;
		a5.right = a6;
		
		System.out.println(isBSTTree(a4));
		
		System.out.println(removeCharacters("fdsfdfaserytdsfdsvxcdsqghfg", "fdse"));
		
		LLinkedList l = new LLinkedList();
		LLinkedList.Node n1 = l.new Node();
		n1.data = "1";
		LLinkedList.Node n2 = l.new Node();
		n2.data = "2";
		LLinkedList.Node n3 = l.new Node();
		n3.data = "3";
		LLinkedList.Node n4 = l.new Node();
		n4.data = "4";
		l.head = n1;
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		
		print(l.head);
		
		//l = LLinkedList.reverseIteratively(l);
		l = LLinkedList.reverseRecursively(l);
		
		print(l.head);
		

		MessageQueue mq = new MessageQueue();
		mq.add("jeden");
		(new Watek(mq)).start();
		Thread.sleep(4000);
		mq.add("dwa");
		System.err.println(mq.remove());
		mq.add("trzy");

		System.err.println(mq.remove());

		Object obj = Class.forName("T").newInstance();
		System.err.println(obj.toString());
		System.err.println(13 % 8);

		ArrayList<Integer> array = new ArrayList<Integer>();
		Set<Integer> set = new HashSet<Integer>(array);

		String a = new String("AA");
		String b = new String("AA");
		System.err.println(a == b);

		System.out.println("1/2=" + 1 / 2);

		System.out.println("Floor=" + Math.floor(-0.5));

		System.out.println("1/2+1/2=" + 1 / 2 + 1 / 2);

		int i = 0;
		int tmp = 1;
		int input = 567;
		while (tmp <= input) {
			if ((tmp & input) > 0) {
				i++;
			}
			tmp *= 2;
		}
		System.err.println("answer is: " + i);
	}
}
